import java.util.Set;
import java.util.Iterator;

/**
 * Search
 */

class SearchStatistic {
    boolean solved;
    long     nodes;
    long     checks;
    long     sec;
}

public class Search {


    enum SearchAlg { // Search algorithm.
        cspBT,   // Backtracking
        cspBJ,   // Backjumping
        cspCDBJ, // Conflict-directed backjumping
        cspBM,   // Backmarking
    }

    private static final long NODES_BETWEEN_CHECKS = 10000;

    // Search management.
    private boolean	  m_abort;
    private long      m_maxTime;
    private long      m_maxNodes;
    private SearchAlg m_searchAlg;

    // Search statistic
    private long      m_nodes;
    private long      m_checks;
    private long      m_nodesSinceLastCheck;
    private long 	  m_startTime;

    Search() {
        m_maxTime   = 300;
        m_maxNodes  = 100000000;
        m_searchAlg = SearchAlg.cspBT;
    }

    // Set/Get various search parameters.
    void setMaxTime( long sec )				{ m_maxTime = sec; }
    void setMaxNodes( long nodes )	    	{ m_maxNodes = nodes; }
    void setSearchMethod( SearchAlg salg )  { m_searchAlg = salg; }

    long getMaxTime()  { return m_maxTime; }
    long getMaxNodes() { return m_maxNodes; }

    // Solve CSP
    void solve( ConstraintSet cs, Domain domain[], int assignment[], SearchStatistic stat ) {
	    m_abort = false;
	    m_nodes = 0;
	    m_nodesSinceLastCheck = 0;
	    m_startTime  = System.currentTimeMillis();
	    cs.resetNumberOfChecks();

    	boolean    solutionFound = false;

    	switch ( m_searchAlg ) {

	    	case cspBT: // Backtracking
		    	solutionFound = BT( 0, cs, domain, assignment );
		    	break;

		    case cspBJ: // Backjumping
			    // ADD YOUR BJ algorithm call here ...
			    break;

		    case cspCDBJ: // Conflict-directed backjumping
                // ADD YOUR CDBJ algorithm call here ...
			    break;

		    case cspBM: // Backmarking
                // ADD YOUR BM algorithm call here ...
			    break;
	    }

	    stat.sec    = (System.currentTimeMillis() - m_startTime) / 1000;
	    stat.solved = solutionFound;
	    stat.nodes  = m_nodes;
        stat.checks = cs.getNumberOfChecks();
    }


    // Help functions
    boolean stop() {
        m_nodesSinceLastCheck++;
        if ( m_nodesSinceLastCheck >= NODES_BETWEEN_CHECKS ) {
            m_nodesSinceLastCheck = 0;
            if ( m_nodes >= m_maxNodes ) {
                return true;
            }
            else {
                long currTime = System.currentTimeMillis();
                long searchTime = ((currTime - m_startTime) / 1000);
                if ( searchTime >= m_maxTime ) {
                    return true;
                }
            }
        }
        return false;
    }


    // Search algorithms.
    boolean BT( int i, ConstraintSet cs, Domain domain[], int assignment[] )
    {
        // Check whether to stop the search because allotted resources (time, nodes) up.
        if ( stop() ) {
            m_abort = true;
            return false;
        }

        // Loop through the domain for the i-th variable.
        m_nodes++;

        for ( Iterator iter=domain[i].iterator(); iter.hasNext(); ) {

            // Assign the varible value from domain, and update puzzle.
            assignment[ i ] = (Integer) iter.next();

            // Check if constraint conflicts.
            boolean consistent = true;
            for ( int h=0 ; h < i && consistent ; ++h ) {
                consistent = cs.test( h, i, assignment );
            }

            // If value is consistent with previous variables then keep on, otherwise try next domain value.
            if ( consistent ) {
                if ( i == cs.getNumberOfVariables() - 1 ) { // At last variable, solution found.
                    return true;
                }
                else {
                    if ( BT( i + 1, cs, domain, assignment ) ) { // Continue recursion down.
                        return true;
                    }
                    if ( m_abort ) return false;
                }
            }

        }

        return false;
    }

    // ... ADD YOUR additional search algorithms here ...
}
